package com.yaxin.b_tree;

import java.util.ArrayList;
import java.util.List;

public class BTree<E> implements Comparable{
	private int maxKeyNum;
	private int t;
	private int minKeyNum;
	private BTNode root;
	private final static int DEFAULT = 2;
	
	public BTree(){
		this(DEFAULT);
	}
	public BTree(int degree){
		if(degree < 2)
			degree = DEFAULT;
		this.t= degree;
		this.minKeyNum = degree - 1;
		this.maxKeyNum = 2*degree - 1;
		BTNode node = new BTNode();
		this.root = node;
	}
	
	public void insert(E key){
		BTNode r = root;
		if(root.n == maxKeyNum){
			
		}else{
			insertNoFull(r,key);
		}
	}
	
	public void insertNoFull(BTNode x,E key){
		int i = x.n - 1;
	}
	
	public void splitChild(BTNode x,int index){
		BTNode z = new BTNode();
		BTNode y = x.children.get(index);
		z.isLeaf = y.isLeaf;
	}

	@Override
	public int compareTo(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	class BTNode{
		// 关键字个数
		public int n = 0;
		public List<E> keys = new ArrayList<E>(maxKeyNum);
		public List<BTNode> children = new ArrayList<BTNode>();
		public boolean isLeaf = true;
		
		public void insertKey(int index,E key){
			keys.add(index,key);
			n++;
			if(keys.size() > maxKeyNum){
				keys.remove(maxKeyNum);
			}
			
		}
		
		public E removeKey(int index){
			E key = keys.remove(index);
			n--;
			return key;
		}
		
		public BTNode insertChild(int index,BTNode child){
			children.add(index,child);
			return child;
		}
	}
}


